| 翻訳と辞書 |
| nested stack automaton ： ウィキペディア英語版 |
nested stack automaton
In automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks.〔 〕
Like a stack automaton, a nested stack automaton may step up or down in the stack, and read the current symbol; in addition, it may at any place create a new stack, operate on that one, eventually destroy it, and continue operating on the old stack. This way, stacks can be nested recursively to an arbitrary depth; however, the automaton always operates on the innermost stack only.
A nested stack automaton is capable of recognizing an indexed language,〔 〕 and in fact the class of indexed languages is exactly the class of languages accepted by one-way nondeterministic nested stack automata.〔〔 Here:p.390〕
Nested stack automata should not be confused with embedded pushdown automata, which have less computational power.
==Formal definition==
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「nested stack automaton」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|